import java.util.List;
import java.util.Stack;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-10
 * Time: 21:49
 */
//class ListNode {
//    int val;
//    ListNode next = null;
//    public ListNode(int val){
//        this.val = val;
//    }
//}
public class Sloution2 {
    /*还有一种方法就是迭代，定义一个新的头结点和一个遍历新链表的节点，从头节点开始进行k个一组的翻转，
    翻转过程中记录每一组尾结点的下一个节点，作为下一组开始翻转的起点
    翻转完一组之后就把新的头结点和这个遍历链表的节点放到下一组
    * */
    //方法：核心是找到第k个和翻转整个链表的思想
    //  1.可以借助虚拟节点构造新的链表，思想是定义一个end找到每一组的第k个之后就断开这一组和下一组的连接，
    //      所以需要先记录下一组的头结点
    //  2.找到第k个节点之后，就利用翻转整个链表的思想翻转这k个，翻转完后必须连接上虚拟节点，
    //   所以要在先定义pre在虚拟节点这，用于连接每一组翻转后的头结点
    //  3.每一组翻转后就需要连接上下一组断开的链表，所以需要先定义每一组翻转前的头结点，翻转后就是尾节点，用于连接下一组
    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode newH=new ListNode(0); //虚拟节点
        newH.next=head;
        ListNode pre=newH; //用于翻转的前驱节点
        ListNode end=newH; //用于翻转的当前节点
        //开始翻转
        while (end.next != null) {
            //找到第k个位置
            for(int i = 0; i <k && end!=null;i++){
                end=end.next;
            }
            //如果end是空，说明不够k个，就不需要反转了，直接退出循环。
            if(end==null){
                break;
            }
            //开始翻转
            ListNode start=pre.next; //fast是每一组翻转前的头结点，翻转后变成每一组最后一个节点，用于连接下一组节点
            //首先需要先记录下一组的头结点
            ListNode nextHead=end.next;
            //然后需要把这组的最后一个节点的后面断开原来的连接
            end.next=null;
            //调用翻转整个链表的翻转函数
            //pre连接的就是翻转后的头结点
            pre.next=reverse(start);
            //翻转完拼接上之前断开的节点
            start.next=nextHead;
            //翻转下一组，end和start应该在上一组的尾结点，这样才方便计算
            pre=start;
            end = start;
        }
        return newH.next;
    }
    //翻转整个链表的逻辑
    public ListNode reverse(ListNode head){
        ListNode tmp=null;
        ListNode cur = head;
        while (cur != null){
            ListNode next=cur.next;
            cur.next=tmp;
            tmp = cur;
            cur = next;
        }
        return tmp;
    }
}
